// @algorithm @lc id=1000037 lang=typescript
// @title get-kth-magic-number-lcci
// @test(6)=14
function getKthMagicNumber(k: number): number {
  const minHeap = new MinHeap();
  const factors = [3, 5, 7];
  const visited = new Set<number>();
  // 初始化
  minHeap.insert(1);
  visited.add(1);

  let ans = 0;
  for (let i = 1; i <= k; i++) {
    ans = minHeap.pop();
    for (const x of factors) {
      const next = ans * x;
      if (!visited.has(next)) {
        minHeap.insert(next);
        visited.add(next);
      }
    }
  }

  return ans;
}

class MinHeap {
  heap: number[];
  constructor() {
    this.heap = [];
  }
  less(i: number, j: number): boolean {
    return this.heap[i] < this.heap[j];
  }
  swap(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
  swin(i: number): void {
    if (i === 0) return;
    const parentIndex = (i - 1) >> 1;
    if (this.heap[parentIndex] > this.heap[i]) {
      this.swap(parentIndex, i);
      this.swin(parentIndex);
    }
  }
  sink(i: number): void {
    const leftIndex = i * 2 + 1;
    const rightIndex = i * 2 + 2;
    if (this.heap[leftIndex] < this.heap[i]) {
      this.swap(leftIndex, i);
      this.sink(leftIndex);
    }
    if (this.heap[rightIndex] < this.heap[i]) {
      this.swap(rightIndex, i);
      this.sink(rightIndex);
    }
  }
  insert(value: number): void {
    this.heap.push(value);
    this.swin(this.heap.length - 1);
  }
  pop(): number {
    this.swap(this.heap.length - 1, 0);
    const val = this.heap.pop();
    this.sink(0);
    return val!;
  }
}
